{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Construct Target Array With Multiple Sums"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isPossible"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #多次求和构造目标数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>target</code> 。一开始，你有一个数组&nbsp;<code>A</code> ，它的所有元素均为 1 ，你可以执行以下操作：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>令&nbsp;<code>x</code>&nbsp;为你数组里所有元素的和</li>\n",
    "\t<li>选择满足&nbsp;<code>0 &lt;= i &lt; target.size</code>&nbsp;的任意下标&nbsp;<code>i</code>&nbsp;，并让&nbsp;<code>A</code>&nbsp;数组里下标为&nbsp;<code>i</code>&nbsp;处的值为&nbsp;<code>x</code>&nbsp;。</li>\n",
    "\t<li>你可以重复该过程任意次</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果能从&nbsp;<code>A</code>&nbsp;开始构造出目标数组&nbsp;<code>target</code>&nbsp;，请你返回 True ，否则返回 False 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>target = [9,3,5]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>从 [1, 1, 1] 开始\n",
    "[1, 1, 1], 和为 3 ，选择下标 1\n",
    "[1, 3, 1], 和为 5， 选择下标 2\n",
    "[1, 3, 5], 和为 9， 选择下标 0\n",
    "[9, 3, 5] 完成\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>target = [1,1,1,2]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>不可能从 [1,1,1,1] 出发构造目标数组。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>target = [8,5]\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>N == target.length</code></li>\n",
    "\t<li><code>1 &lt;= target.length&nbsp;&lt;= 5 * 10^4</code></li>\n",
    "\t<li><code>1 &lt;= target[i] &lt;= 10^9</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [construct-target-array-with-multiple-sums](https://leetcode.cn/problems/construct-target-array-with-multiple-sums/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [construct-target-array-with-multiple-sums](https://leetcode.cn/problems/construct-target-array-with-multiple-sums/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[9,3,5]', '[1,1,1,2]', '[8,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, target: List[int]) -> bool:\n",
    "        n=len(target)\n",
    "        if n==1:return target[0]==1\n",
    "        h=[]\n",
    "        cursum=0\n",
    "        for num in target:\n",
    "            p,r=divmod(num-1,n-1)\n",
    "            if r!=0:return False\n",
    "            heappush(h,-p)\n",
    "            cursum +=p\n",
    "        while h and cursum>0:\n",
    "            # print(h,cursum)\n",
    "            x=-h[0]\n",
    "            rest=cursum-x\n",
    "            # if rest==0:return True\n",
    "            newX=x%(rest+1)\n",
    "            if x==newX:return False\n",
    "            cursum +=newX-x\n",
    "            heapreplace(h,-newX)\n",
    "        return cursum==0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, target: List[int]) -> bool:\n",
    "        if len(target) == 1: return target[0] == 1\n",
    "        while True: \n",
    "            current_x = max(target)\n",
    "            idx = target.index(current_x)\n",
    "            inc = sum(target) - current_x\n",
    "            if current_x == 1 or inc == 1:   # inc 为 1 一定能把所有数变成 1\n",
    "                return True # 最大的数等于 1 了而且数组中无小于 1 的数，那么说明整个数组都是 1，返回 True\n",
    "            target[idx] = current_x % inc\n",
    "            if inc >= current_x or target[idx] == 0: \n",
    "                return False # inc 大于等于 x，这样将会出现小于 1 的值，不是合法情况，返回 False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, target: List[int]) -> bool:\n",
    "        N = len(target)\n",
    "        if N == 1: return target[0] == 1\n",
    "        targetSum, target1s, targetOthers = 0, 0, set()\n",
    "        for n in target:\n",
    "            targetSum += n\n",
    "            if n == 1: target1s += 1\n",
    "            else:\n",
    "                targetOthers.add(n)\n",
    "        if target1s == N: return True\n",
    "        if target1s + len(targetOthers) != N: return False\n",
    "        _sum = sum(target)\n",
    "        h = [-n for n in targetOthers]\n",
    "        heapify(h)\n",
    "        while target1s + 1 < N:\n",
    "            n, n2 = -heappop(h), -heappop(h)\n",
    "            if n == n2: return False\n",
    "            k = (n - n2 + _sum - n -1) // (_sum - n)\n",
    "            # print(n, n2, _sum, k)\n",
    "            n, _sum = n + (n - _sum)*k, n + (n-_sum)*(k-1)\n",
    "            heappush(h, -n2)\n",
    "            if n != 1:\n",
    "                heappush(h, -n)\n",
    "            else:\n",
    "                target1s += 1\n",
    "        return (-h[0]-1)%(N-1) == 0\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, target: List[int]) -> bool:\n",
    "        if len(target) == 1:\n",
    "            return target[0] == 1\n",
    "        target.sort()\n",
    "        sumnum = sum(target)\n",
    "        while target[-1] != 1:\n",
    "            end = target.pop()\n",
    "            yuan = min(end - (sumnum - end) * ((end - target[-1]) // (sumnum - end)), end*2 - sumnum)\n",
    "            if yuan < 1:\n",
    "                return False\n",
    "            sumnum += yuan - end\n",
    "            insort(target, yuan)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, target: List[int]) -> bool:\n",
    "        tot = sum(target)\n",
    "        pq = []\n",
    "        for x in target: heappush(pq, -x)\n",
    "        while pq:\n",
    "            x = -heappop(pq)\n",
    "            if x == 1: return True\n",
    "            if len(pq) < 1: return False\n",
    "            y = -pq[0]\n",
    "            left = tot - x\n",
    "            k = (x - y + left - 1) // left\n",
    "            if k == 0: return False\n",
    "            x -= k * left\n",
    "            if x <= 0: return False\n",
    "            tot -= k * left\n",
    "            heappush(pq, -x)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def isPossible(self, target: List[int]) -> bool:\n",
    "        n, sm = len(target), sum(target)\n",
    "        h = [-num for num in target if num != 1]\n",
    "        heapify(h)\n",
    "        while h:\n",
    "            num = -heappop(h)\n",
    "            sm -= num\n",
    "            if sm == 0: return False\n",
    "            if sm == 1: return True\n",
    "            if num <= sm:\n",
    "                return False\n",
    "            r = num % sm\n",
    "            sm += r\n",
    "            if r != 1:\n",
    "                heappush(h, -r)\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, target: List[int]) -> bool:\n",
    "        tot = sum(target)\n",
    "        pq = []\n",
    "        for x in target: heappush(pq, -x)\n",
    "        while pq:\n",
    "            x = -heappop(pq)\n",
    "            if x == 1: return True\n",
    "            if len(pq) < 1: return False\n",
    "            y = -pq[0]\n",
    "            left = tot - x\n",
    "            k = (x - y + left - 1) // left\n",
    "            if k == 0: return False\n",
    "            x -= k * left\n",
    "            if x <= 0: return False\n",
    "            tot -= k * left\n",
    "            heappush(pq, -x)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, target: List[int]) -> bool:\n",
    "        tot = sum(target)\n",
    "        pq = []\n",
    "        for x in target: heappush(pq, -x)\n",
    "        while pq:\n",
    "            #print(pq)\n",
    "            x = -heappop(pq)\n",
    "            if x == 1: return True\n",
    "            if len(pq) < 1: return False\n",
    "            y = -pq[0]\n",
    "            left = tot - x\n",
    "            k = (x - y + left - 1) // left\n",
    "            if k == 0: return False\n",
    "            x -= k * left\n",
    "            if x <= 0: return False\n",
    "            tot -= k * left\n",
    "            heappush(pq, -x)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, target: List[int]) -> bool:\n",
    "\n",
    "        # the position is non related to the answer\n",
    "        # you must start from the smallest number to construct and build the biggest number at last\n",
    "        # and there cannot have duplicated number to construct except one\n",
    "\n",
    "        # revese build the target\n",
    "\n",
    "        if len(target) == 1:\n",
    "            return target[0] == 1\n",
    "        \n",
    "        cnt1 = target.count(1)\n",
    "\n",
    "        arr = [-v for v in target]\n",
    "        cur_sum = sum(target)\n",
    "        # cur_sum is the original target sum\n",
    "        heapq.heapify(arr)\n",
    "\n",
    "        while cnt1 < len(target):\n",
    "            mx = -heapq.heappop(arr)\n",
    "            second_mx = -arr[0]\n",
    "            \n",
    "            other_sum = cur_sum - mx\n",
    "            \n",
    "            num = max(1, ceil((mx - second_mx) / other_sum))\n",
    "            \n",
    "            mx_origin = mx - other_sum * num\n",
    "            cur_sum = other_sum + mx_origin\n",
    "\n",
    "            if mx_origin < 1:\n",
    "                return False\n",
    "            \n",
    "            if mx_origin == 1:\n",
    "                cnt1 += 1\n",
    "\n",
    "            heapq.heappush(arr, -mx_origin)\n",
    "\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, target: List[int]) -> bool:\n",
    "        if len(target) == 1:\n",
    "            return target[0] == 1\n",
    "\n",
    "        summ = sum(target)\n",
    "        maxHeap = [-num for num in target]\n",
    "        heapq.heapify(maxHeap)\n",
    "\n",
    "        while -maxHeap[0] > 1:\n",
    "            maxi = -heapq.heappop(maxHeap)\n",
    "            restSum = summ - maxi\n",
    "            # Only occurs if n == 2.\n",
    "            if restSum == 1:\n",
    "                return True\n",
    "            updated = maxi % restSum\n",
    "            # Updated == 0 (invalid) or didn't change.\n",
    "            if updated == 0 or updated == maxi:\n",
    "                return False\n",
    "            heapq.heappush(maxHeap, -updated)\n",
    "            summ = summ - maxi + updated\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def isPossible(self, target: List[int]) -> bool:\r\n",
    "        # 最大值不断减小，直到所有值都为1\r\n",
    "        pq = [-x for x in target]\r\n",
    "        heapq.heapify(pq)\r\n",
    "        s = sum(target)\r\n",
    "        while True:\r\n",
    "            x = -heapq.heappop(pq)\r\n",
    "            s -= x\r\n",
    "            if x == 1 or s == 1:\r\n",
    "                return True\r\n",
    "            if x < s or s == 0 or x % s == 0:\r\n",
    "                return False\r\n",
    "            x %= s\r\n",
    "            s += x\r\n",
    "            heapq.heappush(pq, -x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue,Queue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache,cache\n",
    "from string import *\n",
    "from itertools import product\n",
    "from collections import defaultdict\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def isPossible(self, target: List[int]) -> bool:\n",
    "        target.sort()\n",
    "        t = len(target)\n",
    "        if t == 1:\n",
    "            return target[0] == 1\n",
    "        s = sum(target)\n",
    "        pq = PriorityQueue()\n",
    "        for x in target:\n",
    "            pq.put(-x)\n",
    "        while not pq.empty():\n",
    "            x = -pq.get()\n",
    "            if x == 1:\n",
    "                return True\n",
    "            p = -pq.queue[0] \n",
    "            l = 1\n",
    "            r = x\n",
    "            while l < r:\n",
    "                m = (l + r) >> 1\n",
    "                d = (1 + m) * x - m * s\n",
    "                if d <= p:\n",
    "                    r = m\n",
    "                else:\n",
    "                    l = m + 1\n",
    "            d = (1 + l) * x - l * s\n",
    "            if d <= 0:\n",
    "                return False\n",
    "            s -= (x - d)\n",
    "            pq.put(-d)\n",
    "        return False\n",
    "s = Solution()\n",
    "s.isPossible([9,3,5])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, target: List[int]) -> bool:\n",
    "        hq=[]\n",
    "        s=0\n",
    "        for t in target:\n",
    "            s+=t\n",
    "            heapq.heappush(hq,-t)\n",
    "        tmp=heapq.heappop(hq)\n",
    "        while tmp!=-1:\n",
    "            tmp=-tmp\n",
    "            s0=s-tmp\n",
    "            if(tmp<=s-tmp or s0==0):\n",
    "                return False\n",
    "            tmp=tmp%s0\n",
    "            if tmp==0 and s0!=1:\n",
    "                return False\n",
    "            s=s0+tmp\n",
    "            tmp=-tmp\n",
    "            heapq.heappush(hq,tmp)\n",
    "            tmp=heapq.heappop(hq)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, target: List[int]) -> bool:\n",
    "        total = sum(target)\n",
    "        heaq = [-i for i in target]\n",
    "        heapq.heapify(heaq)\n",
    "        while heaq:\n",
    "            cur = -heapq.heappop(heaq)\n",
    "            if cur == 1:\n",
    "                return True\n",
    "            if cur <= total - cur:\n",
    "                return False\n",
    "            total -= cur\n",
    "            if total == 1:\n",
    "                return True\n",
    "            elif total == 0:\n",
    "                return False\n",
    "            cur %= total\n",
    "            if cur == 0:\n",
    "                return False\n",
    "            total += cur\n",
    "            heapq.heappush(heaq, -cur)\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def isPossible(self, target: List[int]) -> bool:\r\n",
    "        if len(target) == 1:\r\n",
    "            return target[0] == 1\r\n",
    "        tot = sum(target)\r\n",
    "        target = [-x for x in target]\r\n",
    "        heapify(target)\r\n",
    "        n = len(target)\r\n",
    "        while tot > n:\r\n",
    "            p = -heappop(target)\r\n",
    "            left = tot - p\r\n",
    "            if left >= p:\r\n",
    "                return False\r\n",
    "\r\n",
    "            tot -= left * (p // left - int(p % left == 0))\r\n",
    "            heappush(target, -left if p % left == 0 else -(p % left))\r\n",
    "        return True\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "正难则反\n",
    "'''\n",
    "class Solution:\n",
    "    def isPossible(self, target: List[int]) -> bool:\n",
    "        if len(target) == 1:\n",
    "            return target[0] == 1 \n",
    "\n",
    "        sums = sum(target)\n",
    "        had = [-x for x in target]\n",
    "        heapq.heapify(had)\n",
    "\n",
    "        while True:\n",
    "            x = -heapq.heappop(had)\n",
    "            if x == 1:\n",
    "                return True\n",
    "            sums -= x\n",
    "\n",
    "            y = max(1, (had[0] + x) // sums)\n",
    "\n",
    "            pre = x - sums * y\n",
    "            \n",
    "            if pre < 1:\n",
    "                return False\n",
    "\n",
    "            sums += pre\n",
    "            heapq.heappush(had, -pre)\n",
    "            #print(had)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "正难则反\n",
    "'''\n",
    "class Solution:\n",
    "    def isPossible(self, target: List[int]) -> bool:\n",
    "        if len(target) == 1:\n",
    "            return target[0] == 1 \n",
    "\n",
    "        sums = sum(target)\n",
    "        had = [-x for x in target]\n",
    "        heapq.heapify(had)\n",
    "\n",
    "        while True:\n",
    "            x = -heapq.heappop(had)\n",
    "            if x == 1:\n",
    "                return True\n",
    "            sums -= x\n",
    "\n",
    "            y = max(1, (had[0] + x + sums - 1) // sums)\n",
    "\n",
    "            pre = x - sums * y\n",
    "            \n",
    "            if pre < 1:\n",
    "                return False\n",
    "\n",
    "            sums += pre\n",
    "            heapq.heappush(had, -pre)\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
